﻿// File: CsoGateway.Collections.SortedList.js
// Version: 0.7.1.0
// Author: Pascal Dufresne
// Date: 2009-03-11
// Last update: 2009-05-25
// http://csogateway.codeplex.com
// http://csogateway.metaobjects.ca
// Copyright (C) 2010 Pascal Dufresne

/*
 * Register CsoGateway.Collections namespace. Import CsoGateway.System namespace.
 */
Type.registerNamespace("CsoGateway.Collections");
ImportNamespace(CsoGateway.System);
  
/*
 * CsoGateway.Collections.SortedList is a collection of key/pair values that are sorted by key. 
 * It's interface is meant to resemble that of the .NET class System.Collections.Generic.SortedList<System.Object>
 *
 * The underlying implementation is a CsoGateway.Collections.Dictionary
 * to keep the key/value pairs and a CsoGateway.Collections.List to keep the keys ordered.
 * 
 * The underlying CsoGateway.Collections.List instance uses Array.sort(Function) to sort the list of keys.
 * The constructor of SortedList can take a 'comparer' function that Array.sort will use to sort the list.
 * If no comparer function is provided, the function ToStringComparer in used. This function sorts the elements of the array in
 * alphabetical order of their toString() representation.
 * The list of keys is sorted only during instantiation, after all keys have been added.
 *
 * The respect of its interface is strictly enforced. All method parameters
 * must be specified, they must be of the right type and within an acceptable
 * range or an exception is thrown.
 *
 * Null values can be added to the SortedList but not undefined values.
 *
 * This class uses the MicrosoftAjax.js Type extensions.
 * It is build on top of the MicrosoftAjax.js library and cannot function without it.
 *
 * Contructor                       'System.Collections.Generic.SortedList<System.Object,System.Object>' equivalent
 * ----------                       -------------------------------------------------------------------------------
 * SortedList()                     SortedList()
 * 
 * SortedList(<argument list>)      SortedList(System.Collections.Generic.IDictionary<System.Object,System.Object>)
 *
 * SortedList(Function,             SortedList(System.Collections.Generic.IDictionary<System.Object,System.Object>,
 * <argument list>)                 System.Collections.Generic.IComparer<System.Object>)
 * 
 *
 *
 * Functions                        'System.Collections.Generic.List<System.Object>' equivalent
 * ----------                       -------------------------------------------------------------------------------
 * Count()                          Count
 * getComparerFunction              Comparer
 * getItem(Object)                  Item{get;}
 * setItem(Object, Object)          Item{set;}
 * Keys()                           Keys
 * Values()                         Values
 * Add(Object,Object)               Add(System.Object,System.Object)
 * Clear()                          Clear()
 * ContainsKey(Object)              ContainsKey(System.Object)
 * ContainsValue(Object)            ContainsValue(System.Object)
 * IndexOfKey(Object)               IndexOfKey(Object)
 * IndexOfValue(Object)             IndexOfValue(Object)
 * Remove(Object)                   Remove(System.Object)
 * RemoveAt(Number)                 RemoveAt(System.Object)
 */

ImportType(CsoGateway.Collections.List);
ImportType(CsoGateway.Collections.Dictionary); 

/*
 * Creates an instance of a CsoGateway.Collections.SortedList. 
 * There are 3 ways to create a SortedList object corresponding to 3 different constructor:
 *
 * - SortedList()
 *		No arguments. A new empty SortedList object is created. The underlying Dictionary will have 32 buckets.
 *		The List of keys will be sorted using the Array.sort() function.
 *		Ref: System.Collections.Generic.SortedList.SortedList()
 *
 * - SortedList(key1, value1, key2, value2 ....)
 *		An even number of arguments of any type. 'keyN' arguments cannot be null or undefined.
 *		The underlying Dictionary object is created with a number of buckets equal to the number of arguments.
 *		Each key/value pair is then inserted in the Dictionary.
 *		Since one key/value pair is 2 arguments, the number of buckets in the Dictionary will be 2 times the initial
 *		number of elements in the Dictionary, making the initial load factor 0.5.
 *		The List of keys will be sorted using the Array.sort() function.
 *		Ref: System.Collections.Generic.SortedList.SortedList(IDictionary)
 *
 * - SortedList(comparerFunction, key1, value1, key2, value2 ....)
 *		An odd number of argument, the first argument is of type Function, the other can be of any type.
 *		If the first argument is not if type Function an exception is thrown. 'keyN' arguments cannot be null or undefined.
 *		The underlying Dictionary object is created with a number of buckets equal to the number of arguments.
 *		Each key/value pair is then inserted in the Dictionary.
 *		Since there is 2 arguments per key/value pair, the number of buckets in the Dictionary will be twice the initial
 *		number of elements in the Dictionary, making the initial load factor 0.5.
 *		The sortFunction argument is a comparer Function that will be used by Array.sort(Function) to sort the underlying
 *		list of key.
 *		Ref: System.Collections.Generic.SortedList.SortedList(IDictionary, IComparer)
 */ 
 
CsoGateway.Collections.SortedList = function SortedList()
{
	if(arguments.length == 0)
	{
		this.innerDictionary = new Dictionary();
		this.innerList = new List();
		this.comparerFunction = ToStringComparer;
	}
	else if((arguments.length % 2) == 0)
	{
		this.innerDictionary = new Dictionary(arguments.length);
		this.innerList = new List();
		this.comparerFunction = ToStringComparer;
	}
	else
	{
		if(!Function.isInstanceOfType(arguments[0]))
			throw new Error('CsoGateway.Collections.SortedList: The number of arguments passed to the constructor is odd but the first ' + 
			'argument is not of type Function');
		
		this.innerDictionary = new Dictionary(arguments.length);
		this.innerList = new List();
		this.comparerFunction = arguments[0];
	}
	

	for(var i=(arguments.length % 2); i<arguments.length; i+=2)
	{
		this.setItem(arguments[i],arguments[i+1]);
	}
	this.innerList.Sort(this.comparerFunction);
}

/*
 * Gets the number of elements actually contained in the SortedList.
 * Ref: System.Collection.Generic.SortedList.Count 
 */
CsoGateway.Collections.SortedList.prototype.Count = function()
{
	return this.innerList.Count();
}

/*
 * Returns the Function object used to sort the list of keys.
 * Ref: System.Collection.Generic.SortedList.Comparer 
 */
CsoGateway.Collections.SortedList.prototype.getComparerFunction =  function()
{
	return this.comparerFunction;
}

/*
 * Gets the value associated with the specified key.
 * Ref: System.Collection.Generic.SortedList.Item
 */
CsoGateway.Collections.SortedList.prototype.getItem =  function(key)
{
	return this.innerDictionary.getItem(key);
}

/*
 * Sets the value associated with the specified key.
 * Ref: System.Collection.Generic.SortedList.Item
 */
CsoGateway.Collections.SortedList.prototype.setItem =  function(key, value)
{
	AssertArgumentNotNullOrUndefined(key, 'key in CsoGateway.Collections.SortedList.prototype.setItem');
	AssertArgumentNotUndefined(value, 'value in CsoGateway.Collections.SortedList.prototype.setItem');

	var indexOfInsertion = BinarySearchCustom(this.innerList.elements, key, true, this.comparerFunction);

	if((indexOfInsertion < this.innerList.Count() && this.innerList.getItem(indexOfInsertion) != key) ||
		indexOfInsertion == this.innerList.Count())
	{
		this.innerList.Insert(indexOfInsertion, key);
	}
	
	this.innerDictionary.setItem(key,value);
}


/*
 * Gets an Array containing the keys in the SortedList
 * Ref: System.Collection.Generic.SortedList.Keys
 */
CsoGateway.Collections.SortedList.prototype.Keys =  function()
{
	return this.innerList.elements.slice();
}

/*
 * Gets an Array containing the values in the SortedList
 * Ref: System.Collection.Generic.SortedList.Values
 */
CsoGateway.Collections.SortedList.prototype.Values =  function()
{
	var valueArray = new Array(this.Count());
	
	for(var i=0; i<this.Count(); ++i)
		valueArray[i] = this.innerDictionary.getItem(this.innerList.getItem(i));
		
	return valueArray;
	
}

/*
 * Adds a key/pair value to the SortedList. Same as the setItem function.
 * Ref: System.Collection.Generic.SortedList.Add
 */
CsoGateway.Collections.SortedList.prototype.Add =  function(key,value)
{
	this.setItem(key,value);
}

/*
 * Removes all key/pair values from the SortedList.
 * Ref: System.Collection.Generic.SortedList.Clear
 */
CsoGateway.Collections.SortedList.prototype.Clear =  function()
{
	this.innerDictionary.Clear();
	this.innerList.Clear();
}


/*
 * Determines whether the SortedList contains the specified key.
 * Ref: System.Collection.Generic.SortedList.ContainsKey
 */
CsoGateway.Collections.SortedList.prototype.ContainsKey =  function(key)
{
	return this.innerDictionary.ContainsKey(key);
}

/*
 * Determines whether the SortedList contains a specific value.
 * Ref: System.Collection.Generic.SortedList.ContainsValue
 */
CsoGateway.Collections.SortedList.prototype.ContainsValue = function(value)
{
	return this.innerDictionary.ContainsValue(value);
}

/*
 * Searches for the specified key and returns the zero-based index within the entire SortedList or -1 is the key is not found.
 * This function performs a binary search; therefore, this function is an O(log n) operation, where n is Count.
 * The same comparer function used to sort the list during instantiation is used to compare objects during the search. 
 * Ref: System.Collection.Generic.SortedList.IndexOfKey
 */
CsoGateway.Collections.SortedList.prototype.IndexOfKey = function(key)
{
	AssertArgumentNotNullOrUndefined(key, 'key in CsoGateway.Collections.SortedList.prototype.IndexOfKey');

	return BinarySearchCustom(this.innerList.elements, key, false, this.comparerFunction);
}

/*
 * Searches for the specified value and returns the zero-based index of the first occurrence within the entire SortedList.
 * This function performs a linear search; therefore, the average execution time is proportional to Count. That is, this function
 * is an O(n) operation, where n is Count.
 * Ref: System.Collection.Generic.SortedList.IndexOfValue
 */
CsoGateway.Collections.SortedList.prototype.IndexOfValue = function(value)
{
	AssertArgumentNotUndefined(value, 'value in CsoGateway.Collections.SortedList.prototype.IndexOfValue');

	for(var i=0; i<this.Count(); ++i)
	{
		if(this.innerDictionary.getItem(this.innerList.getItem(i)) === value)
			return i;
	}
	
	return -1;
}

/*
 * Remove the key/value pair corresponding to the specified key from the SortedList. Return true if the key/value pair was found and removed,
 * return false otherwise.
 * Ref: System.Collection.Generic.SortedList.Remove 
 */
CsoGateway.Collections.SortedList.prototype.Remove = function(key)
{
	AssertArgumentNotNullOrUndefined(key, 'key in CsoGateway.Collections.SortedList.prototype.Remove');

	var indexOfKey = BinarySearchCustom(this.innerList.elements, key, false, this.comparerFunction);

	if((indexOfKey==-1) && !this.innerDictionary.ContainsKey(key))
		return false;
		
	if((indexOfKey==-1) || !this.innerDictionary.ContainsKey(key))
		throw new Error('CsoGateway.Collections.SortedList.Remove: Inconsistent state of the inner Dictionary and List. The key ' + key.toString() + ' is only in one of them');
		
	this.innerList.RemoveAt(indexOfKey);
	this.innerDictionary.Remove(key);
				
	return true;
}

/*
 * Remove the key/value pair at the specified index. Throws an exception if index is not in range.
 * Ref: System.Collection.Generic.SortedList.RemoveAt
 */
CsoGateway.Collections.SortedList.prototype.RemoveAt = function(index)
{
	var removedKey = this.innerList.RemoveAt(index);
	
	if(this.innerDictionary.Remove(removedKey) == null)
		throw new Error('CsoGateway.Collections.SortedList.Remove: Inconsistent state of the inner Dictionary and List. The key ' + key.toString() + ' is only in one of them');
}

/*
 * Register the class CsoGateway.Collections.SortedList
 */
CsoGateway.Collections.SortedList.registerClass('CsoGateway.Collections.SortedList', CsoNative, Sys.IDisposable);

/*
* End of CsoGateway.Collections.List definition
*/
